//
// Created by liushuai on 2020/4/29.
//
#include "checkInclusion.h"
bool checkInclusion(string s1, string s2){
    bool flag = false;
    vector<string> result =permutation(s1);
    for(auto elem:result){
        int match = kmp(s2,elem);
        if(kmp(s2,elem)!=-1){
            flag = true;
            break;
        }
    }
    return flag;
}

vector<int> frequency(string& s1)
{
    vector<int> hash_table(26,0);
    for(auto ch:s1){
        int ch_i = static_cast<int>(ch)-97;
        hash_table[ch_i] +=1;
    }
    return hash_table;
}
bool checkInclusion1(string s1, string s2){
    bool flag = false;
    int length = s1.length();
    vector<int> hash(26,0);
    int last_index = s2.length()-length;
    vector<int> match_freq = frequency(s1);
    for(int start=0;start<last_index+1;start++){
        string slide_str = s2.substr(start,length);
        vector<int> slide_frequency = frequency(slide_str);
        if(slide_frequency == match_freq){
            flag = true;
            break;
        }
    }
    return flag;
}